package NO10_Math;

import java.math.BigInteger;

/**
 * 2025-08-29
 * 力扣 - 172. 阶乘后的零
 * <p>
 * 给定一个整数 n ，返回 n! 结果中尾随零的数量。
 * 提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
 */
public class TrailingZeroesMain {
    public static void main(String[] args) {
        System.out.println(trailingZeroes(13));
        System.out.println(trailingZeroes1(13));
    }

    // 优解
    // 尾随零的数量由因子2和因子5的对数决定，而由于因子2的数量总是多于因子5的数量，所以只需要计算因子5的数量。
    public static int trailingZeroes(int n) {
        // 这是计算阶乘后尾随零数量的数学解法
        // 核心思想：尾随零由因子10产生，而10 = 2 × 5
        // 在阶乘中，因子2的个数总是比因子5多，所以只需计算因子5的个数
        // 算法：不断除以5，统计所有5的倍数、25的倍数(贡献2个5)、125的倍数(贡献3个5)...
        int count = 0;
        while (n > 0) {
            n /= 5;
            count += n;
        }
        return count;
    }

    // 不能直接计算阶乘，会溢出
    public static int trailingZeroes1(int n) {
        BigInteger sum = new BigInteger("1");
        for (int i = 1; i <= n; i++) {
            sum = sum.multiply(BigInteger.valueOf(i));
        }
        int count = 0;
        return count;
    }
}
